1. Field of the Invention
The invention relates to programming language compilers, and more specifically, to a method and apparatus for allocating registers via selective spilling.
2. Description of the Related Art
An important function of an optimizing compiler is allocating physical registers to be used when code instructions generated by the optimizing compiler are executed. Physical registers are actual hardware registers supported by the particular platform on which the code instructions are executed. Ideally, code instructions are executed in the available physical registers without requiring any additional physical registers. However, in many situations, the execution of code instructions requires more than the number of available physical registers.
For example, the execution of a sequence of code instructions may require more intermediate values than the number of available physical registers. In these situations, the physical registers must be allocated to provide for the execution of the code instructions.
One approach for allocating a set of variables to a set of physical registers is known as the graph coloring approach. Generally, the graph coloring approach involves constructing and simplifying a register interference graph for a set of code instructions.
Each variable is represented in the register interference graph as a node. Two nodes are connected when the contents of two variables represented by the nodes cannot simultaneously share a physical register at some point in time during the execution of the code instructions, effectively representing a conflict between the two nodes. Stated another way, two nodes are connected when the contents of two variables represented by the nodes conflict or interfere, i.e., if the variables are ever live simultaneously, or more precisely, if one of the variables is live at a definition point of the other variable.
The register interference graph is then simplified and nodes having fewer connections than the number of available physical registers are removed from the register interference graph. If all of the nodes can be removed from the register interference graph, then a coloring can be determined. That is, all of the variables can be mapped to the available physical registers.
However, sometimes the register interference graph contains one or more nodes having more connections to other nodes than the number of available physical registers. This means that the number of available physical registers is insufficient to store all of the intermediate values specified by the code instructions. Thus, some intermediate values must be stored in other memory.
The process of temporarily storing data from a physical register to another memory location is referred to as “spilling.” Generally, spilling involves performing spill operation(s), followed by one or more reload operations. The spill operation causes data contained in a physical register to be stored in another memory location, such as a runtime stack. Each reload operation causes the data to be loaded or copied from the other memory location into a physical register. Reload operations are performed when the data is required for a calculation.
In terms of the register interference graph, a spill is reflected in the register interference graph by disconnecting the spilled node from all other nodes in the register interference graph. Then the register interference graph is rebuilt and simplified again. Any nodes that have been spilled have no connections to other nodes and are removed from the register interference graph when the register interference graph is simplified. This process is repeated until a mapping of the set of variables to the set of physical registers is achieved.
FIG. 1 is a flow chart 100 illustrating a method for mapping a set of variables to a set of physical registers using the graph coloring approach in accordance with the prior art. From a Start Operation 101, a register interference graph is built in a Build Graph Operation 102. Process flow then moves from Build Graph Operation 102 to a Simplify Operation 104.
In Simplify Operation 104, the register interference graph built in Build Graph Operation 102 is simplified and a stack of nodes to drive a Colorable Operation 106 is produced.
In Colorable Operation 106, a determination is made as to whether the register interference graph built in Build Graph Operation 102 can be colored. If the register interference graph can be colored, then the process is completed in an End Operation 108. On the other hand, if in Colorable Operation 106, the register interference graph cannot be colored, then one or more of the variables is spilled in Insert Spill Code Operation 110, which eliminates the spilled variable(s) as a conflicted node in the register interference graph.
In Build Graph Operation 102, the register interference graph is rebuilt. Operations 102, 104, 106, 110 are repeated until the register interference graph is colored, or are aborted if an infinite loop results.
Although the graph coloring approach set forth above allows a set of variables to be mapped to a set of physical registers, the graph coloring approach has some significant disadvantages. One disadvantage is that spill code instructions must be inserted during Insert Spill Code Operation 110 to perform the spill and reload operations. This increases the overall execution time required to process a sequence of code instructions.
In addition, write and read operations to secondary storage media, such as runtime stacks, often take more time to execute than write and read operations to physical registers, such as Central Processing Unit (CPU) registers. As should be readily apparent, higher efficiency is achieved by minimizing the number of variables spilled.
FIG. 2A is a code block 200 containing references to variables A and B in accordance with the prior art. Code block 200 includes code 202, 204 which define variables A and B, respectively. Code block 200 also includes code 206, 208, which use variables B and A, respectively. Code block 200 may also include other code, which is not illustrated. For purposes of this illustration, assume that only one physical register is available.
FIG. 3 is a register interference graph 300 for code block 200 of FIG. 2A in accordance with the prior art. Referring now to FIGS. 1, 2A and 3 together, from Start Operation 101, register interference graph 300 is built in Build Graph Operation 102. As is well known, variable A is live between code 202, when variable A is defined, and code 208, when variable A is used. Since variable B is defined while variable A is live, there is an interference edge between node A and node B, i.e., an interference edge between node A and node B is defined and node A is connected to node B in register interference graph 300.
FIG. 4 is a flow chart of Simplify Operation 104 of flow chart 100 of FIG. 1 in accordance with the prior art. Referring now to FIGS. 1, 3 and 4 together, from Build Graph Operation 102, Simplify Operation 104 is entered from an Enter Operation 402. From Enter Operation 402, at a Remaining Nodes Operation 404, a determination is made whether there are any remaining nodes in the register interference graph built in Build Graph Operation 102. In this case, it is determined that node A and node B remain in register interference graph 300.
If in Remaining Nodes Operation 404 a determination is made that nodes remain, then in a Node Exist With Degree Less Than The Number of Physical Register Operation 408, hereinafter Operation 408, a determination is made whether a node exists in the register interference graph that has a degree less than the number of physical registers available. The degree of a node is equal to the number of interference edges of the node.
If a determination is made that a node does exist that has a degree less than the number of physical registers available, the node and all of its interference edges are removed from the register interference graph in a Remove Node Operation 410. The removed node is placed in the stack used for Colorable Operation 106.
However, if a determination is made that a node does not exist that has a degree less than the number of physical registers available, then in a Choose Node to Spill Operation 412, a node to be spilled is chosen.
More particularly, in Choose Node to Spill Operation 412, the node with the lowest ratio of spill cost to degree is chosen. This node and all of its interference edges are removed from the register interference graph in Remove Node Operation 410. The removed node is placed in the stack used for Colorable Operation 106.
In this illustration, node A and node B each have a degree of one. Since only a single physical register is available, in Operation 408, a determination is made that a node does not exist that has a degree less than the number of physical registers available.
Since the spill cost and degree of node A is equal to node B, in Choose Node to Spill Operation 412, node A is not distinguishable from node B. Thus, in Choose Node to Spill Operation 412, either node A or node B is chosen randomly.
Assume for purposes of illustration that node B is randomly chosen in Choose Node to Spill Operation 412 and removed in Remove Node Operation 410 and placed in the stack used for Colorable Operation 106. At this point, only node A remains in the register interference graph.
Operations 404, 408, and 410 are then performed to remove node A and place node A in the stack used for Colorable Operation 106. At this point, there are no nodes remaining in the register interference graph.
In Remaining Nodes Operation 404, a determination is made that there are no more remaining nodes. The process then exits at Exit Operation 406 to Colorable Operation 106.
In Colorable Operation 106, an attempt is made to color the register interference graph. More particularly, the register interference graph is rebuilt by inserting each node and its associated interference edges into the register interference graph from the stack built during Simplify Operation 104. Each node and its associated interference edges are inserted in a reverse order from the order the node and its associated interference edges was removed in Simplify Operation 104.
As each node is inserted, the inserted node is colored with the first color that does not appear in any of the nodes connected to the inserted node. These nodes that are connected to the inserted node are sometimes called the inserted node's neighbors. However, if a node is inserted and there is no color available for the inserted node, the inserted node is left uncolored. This process is repeated until all nodes are inserted into the register interference graph.
If all of the nodes are inserted and colored during Colorable Operation 106, the register interference graph is colored and process flow moves to End Operation 108. However, if all of the nodes are inserted and one or more of the nodes are uncolored during Colorable Operation 106, the register interference graph is uncolored and process flow moves to Insert Spill Code Operation 110.
In Insert Spill Code Operation 110, code to spill the variable chosen in Simplify Operation 104 and which is left uncolored in Colorable Operation 106 is generated. After generation of the spill code, the chosen node is sometimes called a spilled node.
From Insert Spill Code Operation 110, in Build Graph Operation 102, the register interference graph is rebuilt. However, this time the register interference graph is rebuilt with the spilled node disconnected from all the other nodes in the register interference graph.
In this illustration, since node B was removed first in Simplify Operation 104 as discussed above, node A is inserted into the register interference graph and colored during Colorable Operation 106. Next, node B is inserted into the register interference graph. However, since there is only a single physical register, i.e., only a single color available, and this color is already taken by node A, there is no color available for node B. Consequently, node B is left uncolored.
Since node B is left uncolored during Colorable Operation 106, the register interference graph is uncolored and process flow moves to Insert Spill Code Operation 110. In Insert Spill Code Operation 110, code to spill variable B is generated.
FIG. 2B is code block 200 of FIG. 2A including additional code for spilling variable B in accordance with the prior art. Referring now to FIGS. 1 and 2B together, during Insert Spill Code Operation 110, code 210 is added immediately following code 204, to perform a spill operation on variable B. As previously discussed, the spill operation writes variable B from a physical register to another memory location, such as a runtime stack.
In addition, code 212 has been added immediately before code 206 to perform a reload operation on variable B, which causes spilled variable B to be reloaded as variable B′. Code 206 then uses the reloaded variable B′.
FIG. 5 is a register interference graph 500 for code block 200 of FIG. 2B in accordance with the prior art. Referring now to FIGS. 1, 2B and 5 together, from Insert Spill Code Operation 110, register interference graph 500 is built in Build Graph Operation 102. Variable A is still live between the code 202 and code 208. Since variables B, B′ are defined while variable A is live, there is an interference edge between node A and node B and between node A and node B′, i.e., node A is connected to both node B and node B′ in register interference graph 500.
As should be readily apparent, register interference graph 500 is not colorable with a single physical register. Thus, in the above illustration, code 210, 212 was needlessly inserted thus reducing efficiency of the compiler.